{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #二叉树灯饰"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #dynamic-programming #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #动态规划 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: closeLampInTree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #二叉树灯饰"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>「力扣嘉年华」的中心广场放置了一个巨型的二叉树形状的装饰树。每个节点上均有一盏灯和三个开关。节点值为&nbsp;<code>0</code> 表示灯处于「关闭」状态，节点值为 <code>1</code>&nbsp;表示灯处于「开启」状态。每个节点上的三个开关各自功能如下：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>开关 <code>1</code>：切换当前节点的灯的状态；</li>\n",
    "\t<li>开关 <code>2</code>：切换 <strong>以当前节点为根</strong>&nbsp;的子树中，所有节点上的灯的状态；</li>\n",
    "\t<li>开关 <code>3</code>：切换 <strong>当前节点及其左右子节点</strong>（若存在的话） 上的灯的状态；</li>\n",
    "</ul>\n",
    "\n",
    "<p>给定该装饰的初始状态 <code>root</code>，请返回最少需要操作多少次开关，可以关闭所有节点的灯。</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1,1,0,null,null,null,1]\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>以下是最佳的方案之一，如图所示\n",
    "<img alt=\"\" src=\"https://pic.leetcode-cn.com/1629357030-GSbzpY-b71b95bf405e3b223e00b2820a062ba4.gif\" style=\"width: 300px; height: 225px;\" />\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1,1,1,1,null,null,1]\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>以下是最佳的方案，如图所示\n",
    "<img alt=\"\" src=\"https://pic.leetcode-cn.com/1629356950-HZsKZC-a4091b6448a0089b4d9e8f0390ff9ac6.gif\" style=\"width: 300px; height: 225px;\" />\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [0,null,0]\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>无需操作开关，当前所有节点上的灯均已关闭\n",
    "</pre>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= 节点个数 &lt;= 10^5</code></li>\n",
    "\t<li><code>0 &lt;= Node.val &lt;= 1</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [U7WvvU](https://leetcode.cn/problems/U7WvvU/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [U7WvvU](https://leetcode.cn/problems/U7WvvU/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,1,0,null,null,null,1]', '[1,1,1,1,null,null,1]', '[0,null,0]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def closeLampInTree(self, root: TreeNode) -> int:\n",
    "        #树形DP\n",
    "        #dp[0]表示全亮的操作数\n",
    "        #dp[1]表示全灭的操作数\n",
    "        #dp[2]表示根亮子树灭的操作数\n",
    "        #dp[3]表示根灭子树亮的操作数\n",
    "        def dfs(x):\n",
    "            if x is None:\n",
    "                return [0,0,0,0]\n",
    "            l=dfs(x.left)\n",
    "            r=dfs(x.right)\n",
    "            dp=[0]*4\n",
    "            #考虑状态转移,CPU烧了\n",
    "            #当前灯亮\n",
    "            if x.val==1:\n",
    "                dp[0]=min(l[0]+r[0],2+l[1]+r[1],2+l[2]+r[2],2+l[3]+r[3])\n",
    "                dp[1]=min(1+l[0]+r[0],1+l[1]+r[1],1+l[2]+r[2],3+l[3]+r[3])\n",
    "                dp[2]=min(2+l[0]+r[0],l[1]+r[1],2+l[2]+r[2],2+l[3]+r[3])\n",
    "                dp[3]=min(1+l[0]+r[0],1+l[1]+r[1],3+l[2]+r[2],1+l[3]+r[3])\n",
    "            #当前灯灭\n",
    "            else:\n",
    "                dp[0]=min(1+l[0]+r[0],1+l[1]+r[1],3+l[2]+r[2],1+l[3]+r[3])\n",
    "                dp[1]=min(l[0]+r[0]+2,l[1]+r[1],2+l[2]+r[2],2+l[3]+r[3])\n",
    "                dp[2]=min(1+l[0]+r[0],1+l[1]+r[1],1+l[2]+r[2],3+l[3]+r[3])\n",
    "                dp[3]=min(l[0]+r[0],2+l[1]+r[1],2+l[2]+r[2],2+l[3]+r[3])\n",
    "            return dp\n",
    "        return dfs(root)[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def closeLampInTree(self, root: TreeNode) -> int:\n",
    "        #树形DP\n",
    "        #dp[0]表示全亮的操作数\n",
    "        #dp[1]表示全灭的操作数\n",
    "        #dp[2]表示根亮子树灭的操作数\n",
    "        #dp[3]表示根灭子树亮的操作数\n",
    "        def dfs(x):\n",
    "            if x is None:\n",
    "                return [0,0,0,0]\n",
    "            l=dfs(x.left)\n",
    "            r=dfs(x.right)\n",
    "            dp=[0]*4\n",
    "            #考虑状态转移,CPU烧了\n",
    "            #当前灯亮\n",
    "            if x.val==1:\n",
    "                dp[0]=min(l[0]+r[0],2+l[1]+r[1],2+l[2]+r[2],2+l[3]+r[3])\n",
    "                dp[1]=min(1+l[0]+r[0],1+l[1]+r[1],1+l[2]+r[2],3+l[3]+r[3])\n",
    "                dp[2]=min(2+l[0]+r[0],l[1]+r[1],2+l[2]+r[2],2+l[3]+r[3])\n",
    "                dp[3]=min(1+l[0]+r[0],1+l[1]+r[1],3+l[2]+r[2],1+l[3]+r[3])\n",
    "            #当前灯灭\n",
    "            else:\n",
    "                dp[0]=min(1+l[0]+r[0],1+l[1]+r[1],3+l[2]+r[2],1+l[3]+r[3])\n",
    "                dp[1]=min(l[0]+r[0]+2,l[1]+r[1],2+l[2]+r[2],2+l[3]+r[3])\n",
    "                dp[2]=min(1+l[0]+r[0],1+l[1]+r[1],1+l[2]+r[2],3+l[3]+r[3])\n",
    "                dp[3]=min(l[0]+r[0],2+l[1]+r[1],2+l[2]+r[2],2+l[3]+r[3])\n",
    "            return dp\n",
    "        return dfs(root)[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def closeLampInTree(self, root: TreeNode) -> int:\n",
    "        def dfs(c):\n",
    "            if not c:\n",
    "                return 0,0,0,0\n",
    "            l1,l2,l3,l4 = dfs(c.left)\n",
    "            r1,r2,r3,r4 = dfs(c.right)\n",
    "            if c.val:\n",
    "               t1 = min(l1 + r1,2 + l2 + r2,2 + l3 + r3,2 + l4 + r4)\n",
    "               t2 = min(1 + l2 + r2,l1 + r1 + 1,l3 + r3 + 1,l4 + r4 + 3)\n",
    "               t3 = min(l1 + r1 + 2,l2 + r2,l3 + r3 + 2,l4 + r4 + 2)\n",
    "               t4 = min(l1 + r1 + 1,l2 + r2 + 1,l3 + r3 + 3,l4 + r4 + 1)\n",
    "            else:\n",
    "               t1 = min(l1 + r1 + 1,1 + l2 + r2,3 + l3 + r3,1 + l4 + r4)\n",
    "               t2 = min(l2 + r2,l1 + r1 + 2,l3 + r3 + 2,l4 + r4 + 2)\n",
    "               t3 = min(l1 + r1 + 1,l2 + r2 + 1,l3 + r3 + 1,l4 + r4 + 3)\n",
    "               t4 = min(l1 + r1,l2 + r2 + 2,l3 + r3 + 2,l4 + r4 + 2)\n",
    "            return t1,t2,t3,t4\n",
    "        \n",
    "        ans = dfs(root)\n",
    "        return ans[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def closeLampInTree(self, root: TreeNode) -> int:\n",
    "        def dfs(c):\n",
    "            if not c:\n",
    "                return 0,0,0,0\n",
    "            l0,l1,l2,l3 = dfs(c.left)\n",
    "            r0,r1,r2,r3 = dfs(c.right)\n",
    "            if c.val == 1: # 当前根节点为亮\n",
    "            #// 2 + l1 + r1：左右子树全灭, 用2个操作使他们全亮，这样一共花费2 + l1 + r1使得当前子树所有节点全亮，状态转移到t0\n",
    "               t0 = min(l0 + r0,   l1 + r1+2, l2 + r2+2, l3 + r3+2)\n",
    "               t1 = min(l0 + r0+1, l1 + r1+1, l2 + r2+1, l3 + r3+3)\n",
    "               t2 = min(l0 + r0+2, l1 + r1,   l2 + r2+2, l3 + r3+2)\n",
    "               t3 = min(l0 + r0+1, l1 + r1+1, l2 + r2+3, l3 + r3+1)\n",
    "            else: #当前根节点是灭的\n",
    "               t0 = min(l0 + r0+1, l1 + r1+1, l2 + r2+3, l3 + r3+1)\n",
    "               t1 = min(l0 + r0+2, l1 + r1,   l2 + r2+2, l3 + r3+2)\n",
    "               t2 = min(l0 + r0+1, l1 + r1+1, l2 + r2+1, l3 + r3+3)\n",
    "               t3 = min(l0 + r0,   l1 + r1+2, l2 + r2+2, l3 + r3+2)\n",
    "            return t0,t1,t2,t3\n",
    "        \n",
    "        res = dfs(root)\n",
    "        return res[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def closeLampInTree(self, root: TreeNode) -> int:\n",
    "        # 1:全亮 2:全灭 3:当前灯亮,其余全灭 4:当前灯灭,其余全亮\n",
    "        def dfs(c):\n",
    "            if not c:\n",
    "                return 0,0,0,0\n",
    "            l1,l2,l3,l4 = dfs(c.left)\n",
    "            r1,r2,r3,r4 = dfs(c.right)\n",
    "            if c.val:\n",
    "               t1 = min(l1 + r1,2 + l2 + r2,2 + l3 + r3,2 + l4 + r4)\n",
    "               t2 = min(1 + l2 + r2,l1 + r1 + 1,l3 + r3 + 1,l4 + r4 + 3)\n",
    "               t3 = min(l1 + r1 + 2,l2 + r2,l3 + r3 + 2,l4 + r4 + 2)\n",
    "               t4 = min(l1 + r1 + 1,l2 + r2 + 1,l3 + r3 + 3,l4 + r4 + 1)\n",
    "            else:\n",
    "               t1 = min(l1 + r1 + 1,1 + l2 + r2,3 + l3 + r3,1 + l4 + r4)\n",
    "               t2 = min(l2 + r2,l1 + r1 + 2,l3 + r3 + 2,l4 + r4 + 2)\n",
    "               t3 = min(l1 + r1 + 1,l2 + r2 + 1,l3 + r3 + 1,l4 + r4 + 3)\n",
    "               t4 = min(l1 + r1,l2 + r2 + 2,l3 + r3 + 2,l4 + r4 + 2)\n",
    "            return t1,t2,t3,t4\n",
    "        \n",
    "        ans = dfs(root)\n",
    "        return ans[1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def closeLampInTree(self, root: TreeNode) -> int:\n",
    "        def dfs(c):\n",
    "            if not c:\n",
    "                return 0,0,0,0\n",
    "            l0,l1,l2,l3 = dfs(c.left)\n",
    "            r0,r1,r2,r3 = dfs(c.right)\n",
    "            if c.val == 1: # 当前根节点为亮\n",
    "            #// 2 + l1 + r1：左右子树全灭, 用2个操作使他们全亮，这样一共花费2 + l1 + r1使得当前子树所有节点全亮，状态转移到t0\n",
    "               t0 = min(l0 + r0, 2 + l1 + r1, 2 + l2 + r2, 2 + l3 + r3)\n",
    "               t1 = min(1 + l1 + r1, l0 + r0 + 1, l2 + r2 + 1, l3 + r3 + 3)\n",
    "               t2 = min(l0 + r0 + 2,l1 + r1, l2 + r2 + 2, l3 + r3 + 2)\n",
    "               t3 = min(l0 + r0 + 1,l1 + r1 + 1, l2 + r2 + 3, l3 + r3 + 1)\n",
    "            else: #当前根节点是灭的\n",
    "               t0 = min(l0 + r0 + 1,1 + l1 + r1, 3 + l2 + r2, 1 + l3 + r3)\n",
    "               t1 = min(l1 + r1, l0 + r0 + 2, l2 + r2 + 2, l3 + r3 + 2)\n",
    "               t2 = min(l0 + r0 + 1, l1 + r1 + 1, l2 + r2 + 1, l3 + r3 + 3)\n",
    "               t3 = min(l0 + r0, l1 + r1 + 2, l2 + r2 + 2, l3 + r3 + 2)\n",
    "            return t0,t1,t2,t3\n",
    "        \n",
    "        res = dfs(root)\n",
    "        return res[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def closeLampInTree(self, root: TreeNode) -> int:\n",
    "        def dfs(c):\n",
    "            if not c:\n",
    "                return 0,0,0,0\n",
    "            l1,l2,l3,l4 = dfs(c.left)\n",
    "            r1,r2,r3,r4 = dfs(c.right)\n",
    "            if c.val:\n",
    "                t1=min(l1+r1,l2+r2+2,l3+r3+2,l4+r4+2)\n",
    "                t2 = min(1 + l2 + r2,l1 + r1 + 1,l3 + r3 + 1,l4 + r4 + 3)\n",
    "                t3 = min(l1 + r1 + 2,l2 + r2,l3 + r3 + 2,l4 + r4 + 2)\n",
    "                t4 = min(l1 + r1 + 1,l2 + r2 + 1,l3 + r3 + 3,l4 + r4 + 1)\n",
    "\n",
    "            else:\n",
    "                t1=min(l1+r1+1,l2+r2+1,l3+r3+3,l4+r4+1)\n",
    "                t2 = min(l2 + r2,l1 + r1 + 2,l3 + r3 + 2,l4 + r4 + 2)\n",
    "                t3 = min(l1 + r1 + 1,l2 + r2 + 1,l3 + r3 + 1,l4 + r4 + 3)\n",
    "                t4 = min(l1 + r1,l2 + r2 + 2,l3 + r3 + 2,l4 + r4 + 2)\n",
    "            return t1,t2,t3,t4\n",
    "        ans=dfs(root)\n",
    "        return ans[1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def closeLampInTree(self, root: TreeNode) -> int:\n",
    "        def dfs(c):\n",
    "            if not c:\n",
    "                return 0,0,0,0\n",
    "            l0,l1,l2,l3 = dfs(c.left)\n",
    "            r0,r1,r2,r3 = dfs(c.right)\n",
    "            if c.val:\n",
    "               t0 = min(l0 + r0, 2 + l1 + r1, 2 + l2 + r2, 2 + l3 + r3)\n",
    "               t1 = min(1 + l1 + r1, l0 + r0 + 1, l2 + r2 + 1, l3 + r3 + 3)\n",
    "               t2 = min(l0 + r0 + 2,l1 + r1, l2 + r2 + 2, l3 + r3 + 2)\n",
    "               t3 = min(l0 + r0 + 1,l1 + r1 + 1, l2 + r2 + 3, l3 + r3 + 1)\n",
    "            else:\n",
    "               t0 = min(l0 + r0 + 1,1 + l1 + r1, 3 + l2 + r2, 1 + l3 + r3)\n",
    "               t1 = min(l1 + r1, l0 + r0 + 2, l2 + r2 + 2, l3 + r3 + 2)\n",
    "               t2 = min(l0 + r0 + 1, l1 + r1 + 1, l2 + r2 + 1, l3 + r3 + 3)\n",
    "               t3 = min(l0 + r0, l1 + r1 + 2, l2 + r2 + 2, l3 + r3 + 2)\n",
    "            return t0,t1,t2,t3\n",
    "        \n",
    "        ans = dfs(root)\n",
    "        return ans[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def closeLampInTree(self, root: TreeNode) -> int:\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return 0,0,0,0\n",
    "            l1,l2,l3,l4=dfs(root.left)\n",
    "            r1,r2,r3,r4=dfs(root.right)\n",
    "            if root.val:\n",
    "                t1=min(l1+r1,2+l2+r2,2+l3+r3,2+l4+r4)\n",
    "                t2=min(1+l2+r2,1+l1+r1,1+l3+r3,3+l4+r4)\n",
    "                t3=min(l1+r1+2,l2+r2,l3+r3+2,l4+r4+2)\n",
    "                t4=min(l1+r1+1,l2+r2+1,l3+r3+3,l4+r4+1)\n",
    "            else:\n",
    "                t1=min(l1+r1+1,1+l2+r2,l3+r3+3,l4+r4+1)\n",
    "                t2=min(l2+r2,l1+r1+2,l3+r3+2,l4+r4+2)\n",
    "                t3=min(l1+r1+1,l2+r2+1,l3+r3+1,l4+r4+3)\n",
    "                t4=min(l1+r1,l2+r2+2,l3+r3+2,l4+r4+2)\n",
    "            return t1,t2,t3,t4\n",
    "        return dfs(root)[1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def closeLampInTree(self, root: TreeNode) -> int:\n",
    "        \n",
    "        # 1:全亮 2:全灭 3:当前灯亮,其余全灭 4:当前灯灭,其余全亮\n",
    "        def dfs(c):\n",
    "            if not c:\n",
    "                return 0,0,0,0\n",
    "            l1,l2,l3,l4 = dfs(c.left)\n",
    "            r1,r2,r3,r4 = dfs(c.right)\n",
    "            if c.val:\n",
    "               t1 = min(l1 + r1,2 + l2 + r2,2 + l3 + r3,2 + l4 + r4)\n",
    "               t2 = min(1 + l2 + r2,l1 + r1 + 1,l3 + r3 + 1,l4 + r4 + 3)\n",
    "               t3 = min(l1 + r1 + 2,l2 + r2,l3 + r3 + 2,l4 + r4 + 2)\n",
    "               t4 = min(l1 + r1 + 1,l2 + r2 + 1,l3 + r3 + 3,l4 + r4 + 1)\n",
    "            else:\n",
    "               t1 = min(l1 + r1 + 1,1 + l2 + r2,3 + l3 + r3,1 + l4 + r4)\n",
    "               t2 = min(l2 + r2,l1 + r1 + 2,l3 + r3 + 2,l4 + r4 + 2)\n",
    "               t3 = min(l1 + r1 + 1,l2 + r2 + 1,l3 + r3 + 1,l4 + r4 + 3)\n",
    "               t4 = min(l1 + r1,l2 + r2 + 2,l3 + r3 + 2,l4 + r4 + 2)\n",
    "            return t1,t2,t3,t4\n",
    "        \n",
    "        ans = dfs(root)\n",
    "        return ans[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closeLampInTree(self, root: TreeNode) -> int:\n",
    "        def dfs(rt):\n",
    "            if rt is None: return (0, 0, 0, 0)\n",
    "            (la, lb, lc, ld) = dfs(rt.left)\n",
    "            (ra, rb, rc, rd) = dfs(rt.right)\n",
    "            v = rt.val > 0\n",
    "            x = min((la + ra + (1 if v else 0), lb + rb + (1 if v else 2), lc + rc + (1 if v else 2),\n",
    "                     ld + rd + (3 if v else 2)))\n",
    "            y = min((la + ra + (0 if v else 1), lb + rb + (2 if v else 1), lc + rc + (2 if v else 1),\n",
    "                     ld + rd + (2 if v else 3)))\n",
    "            z = min((la + ra + (2 if v else 1), lb + rb + (2 if v else 3), lc + rc + (0 if v else 1),\n",
    "                     ld + rd + (2 if v else 1)))\n",
    "            k = min((la + ra + (1 if v else 2), lb + rb + (3 if v else 2), lc + rc + (1 if v else 0),\n",
    "                     ld + rd + (1 if v else 2)))\n",
    "            return (x, y, z, k)\n",
    "\n",
    "        (x, y, z, k) = dfs(root)\n",
    "        return min(x, y + 1, z + 1, k + 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def closeLampInTree(self, root: TreeNode) -> int:\n",
    "\n",
    "        def get_by_flag(flag, v1, v2):\n",
    "            if flag:\n",
    "                return v1\n",
    "            return v2\n",
    "\n",
    "        def dfs(root):\n",
    "            if root is None:\n",
    "                return 0, 0, 0, 0\n",
    "            # 全灭 根亮 全亮 除了根全亮\n",
    "            la, lb, lc, ld = dfs(root.left)\n",
    "            ra, rb, rc, rd = dfs(root.right)\n",
    "            flag = root.val == 1\n",
    "\n",
    "            # 计算全灭\n",
    "            rootA = min(\n",
    "                la + ra + get_by_flag(flag, 1, 0), \n",
    "                lb + rb + get_by_flag(flag, 1, 2),\n",
    "                lc + rc + get_by_flag(flag, 1, 2),\n",
    "                ld + rd + get_by_flag(flag, 3, 2),\n",
    "            )\n",
    "\n",
    "            # 计算根亮\n",
    "            rootB = min(\n",
    "                la + ra + get_by_flag(flag, 0, 1),\n",
    "                lb + rb + get_by_flag(flag, 2, 1),\n",
    "                lc + rc + get_by_flag(flag, 2, 1),\n",
    "                ld + rd + get_by_flag(flag, 2, 3),\n",
    "            )\n",
    "\n",
    "            # 计算全亮\n",
    "            rootC = min(\n",
    "                la + ra + get_by_flag(flag, 2, 1),\n",
    "                lb + rb + get_by_flag(flag, 2, 3),\n",
    "                lc + rc + get_by_flag(flag, 0, 1),\n",
    "                ld + rd + get_by_flag(flag, 2, 1),\n",
    "            )\n",
    "\n",
    "            # 计算除了根全亮\n",
    "            rootD = min(\n",
    "                la + ra + get_by_flag(flag, 1, 2),\n",
    "                lb + rb + get_by_flag(flag, 3, 2),\n",
    "                lc + rc + get_by_flag(flag, 1, 0),\n",
    "                ld + rd + get_by_flag(flag, 1, 2),\n",
    "            )\n",
    "            return rootA, rootB, rootC, rootD\n",
    "        a, b, c, d = dfs(root)\n",
    "        return min(a, b + 1, c + 1, d + 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def closeLampInTree(self, root: TreeNode) -> int:\n",
    "        def dfs(root: TreeNode) -> List[int]:\n",
    "            if not root:\n",
    "                return [0, 0, 0, 0]\n",
    "            \"\"\"\n",
    "            总共四种状态:\n",
    "            0: 以当前节点为根,全灭\n",
    "            1: 以当前节点为根,全亮\n",
    "            2: 根亮, 子树灭\n",
    "            3: 根灭, 子树亮\n",
    "            \"\"\"\n",
    "            ans = [0] * 4\n",
    "            op = 0 if root.val == 1 else 1\n",
    "            ou = 0 if root.val == 0 else 1\n",
    "            lf, rf = dfs(root.left), dfs(root.right)\n",
    "            ans[0] = min(ou + lf[0] + rf[0], op + lf[1] + rf[1] + 1, op + lf[2] + rf[2] + 1, ou + lf[3] + rf[3] + 2)\n",
    "            ans[1] = min(ou + lf[0] + rf[0] + 1, op + lf[1] + rf[1], op + lf[2] + rf[2] + 2, ou + lf[3] + rf[3] + 1)\n",
    "            ans[2] = min(op + lf[0] + rf[0], ou + lf[1] + rf[1] + 1, ou + lf[2] + rf[2] + 1, op + lf[3] + rf[3] + 2)\n",
    "            ans[3] = min(op + lf[0] + rf[0] + 1, ou + lf[1] + rf[1], ou + lf[2] + rf[2] + 2, op + lf[3] + rf[3] + 1)\n",
    "            return ans\n",
    "\n",
    "        return dfs(root)[0]\n",
    "    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def closeLampInTree(self, root: TreeNode) -> int:\n",
    "        def dfs(nd):\n",
    "            dp = [0]*4\n",
    "            if not nd:\n",
    "                return dp  # null节点\n",
    "            x,y=nd.val,1-nd.val\n",
    "            a,b,c,d = [sum(c) for c in zip(dfs(nd.left) , dfs(nd.right))]\n",
    "            # [1,0,1,1,1,0,null,null,1]\n",
    "            # 考虑对称最优性(设4种状态都由子树对称状态转化最优), 并且由叶子出发向上一定能取得最优解\n",
    "            dp[0]=min(a+y  ,b+y+2,c+x+1,d+x+1)\n",
    "            dp[1]=min(a+x+1,b+x+1,c+y  ,d+y+2)\n",
    "            dp[2]=min(a+y+1,b+y+1,c+x  ,d+x+2)\n",
    "            dp[3]=min(a+x  ,b+x+2,c+y+1,d+y+1)\n",
    "            return dp\n",
    "        a,b,c,d = dfs(root)\n",
    "        return min(a+1,b+1,c,d+2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def closeLampInTree(self, root: TreeNode) -> int:\n",
    "        def dp(node):\n",
    "            # oo,oc,co,cc\n",
    "            if not node: return 0,0,0,0\n",
    "            l,r = map(dp,[node.left,node.right])\n",
    "            x = node.val\n",
    "            oo = min(l[0]+r[0]+1-x,l[1]+r[1]+3-x,l[2]+r[2]+1+x,l[3]+r[3]+1+x)\n",
    "            oc = min(l[0]+r[0]+1+x,l[1]+r[1]+1+x,l[2]+r[2]+3-x,l[3]+r[3]+1-x)\n",
    "            co = min(l[0]+r[0]+x,l[1]+r[1]+2+x,l[2]+r[2]+2-x,l[3]+r[3]+2-x)\n",
    "            cc = min(l[0]+r[0]+2-x,l[1]+r[1]+2-x,l[2]+r[2]+2+x,l[3]+r[3]+x)\n",
    "            return oo,oc,co,cc\n",
    "        return dp(root)[3]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def closeLampInTree(self, root: TreeNode) -> int:\n",
    "        @cache\n",
    "        def dfs(c):\n",
    "            if not c:\n",
    "                return 0,0,0,0\n",
    "            l0,l1,l2,l3 = dfs(c.left)\n",
    "            r0,r1,r2,r3 = dfs(c.right)\n",
    "            if c.val == 1: # 当前根节点为亮\n",
    "            #// 2 + l1 + r1：左右子树全灭, 用2个操作使他们全亮，这样一共花费2 + l1 + r1使得当前子树所有节点全亮，状态转移到t0\n",
    "               t0 = min(l0 + r0, 2 + l1 + r1, 2 + l2 + r2, 2 + l3 + r3)\n",
    "               t1 = min(1 + l1 + r1, l0 + r0 + 1, l2 + r2 + 1, l3 + r3 + 3)\n",
    "               t2 = min(l0 + r0 + 2,l1 + r1, l2 + r2 + 2, l3 + r3 + 2)\n",
    "               t3 = min(l0 + r0 + 1,l1 + r1 + 1, l2 + r2 + 3, l3 + r3 + 1)\n",
    "            else: #当前根节点是灭的\n",
    "               t0 = min(l0 + r0 + 1,1 + l1 + r1, 3 + l2 + r2, 1 + l3 + r3)\n",
    "               t1 = min(l1 + r1, l0 + r0 + 2, l2 + r2 + 2, l3 + r3 + 2)\n",
    "               t2 = min(l0 + r0 + 1, l1 + r1 + 1, l2 + r2 + 1, l3 + r3 + 3)\n",
    "               t3 = min(l0 + r0, l1 + r1 + 2, l2 + r2 + 2, l3 + r3 + 2)\n",
    "            return t0,t1,t2,t3\n",
    "        \n",
    "        res = dfs(root)\n",
    "        return res[1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def closeLampInTree(self, root: TreeNode) -> int:\n",
    "        @cache\n",
    "        def dp(node, switch2, switch3):\n",
    "            if not node:\n",
    "                return 0\n",
    "            left, right = node.left, node.right\n",
    "            if (node.val + switch2 + switch3) & 1:\n",
    "                res = dp(left, 0, switch3) + dp(right, 0, switch3) + 1\n",
    "                res = min(res, dp(left, 1, switch3) + dp(right, 1, switch3)  + 1)\n",
    "                res = min(res, dp(left, 0, switch3 ^ 1) + dp(right, 0, switch3 ^ 1)  + 1)\n",
    "                res = min(res, dp(left, 1, switch3 ^ 1) + dp(right, 1, switch3 ^ 1)  + 3)\n",
    "            else:\n",
    "                # 当前灯开着\n",
    "                res = dp(left, 1, switch3) + dp(right, 1, switch3) + 2\n",
    "                res = min(res, dp(left, 0, switch3 ^ 1) + dp(right, 0, switch3 ^ 1) + 2)\n",
    "                res = min(res, dp(left, 1, switch3 ^ 1) + dp(right, 1, switch3 ^ 1) + 2)\n",
    "                res = min(res, dp(left, 0, switch3) + dp(right, 0, switch3))                \n",
    "            return res\n",
    "        \n",
    "        return dp(root, 0, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def closeLampInTree(self, root: TreeNode) -> int:\n",
    "        @cache  # 记忆化搜索\n",
    "        def f(node: TreeNode, switch2: bool, switch3: bool) -> int:\n",
    "            if node is None:\n",
    "                return 0\n",
    "            if (node.val == 1) == (switch2 == switch3):  # 当前节点为开灯\n",
    "                res1 = f(node.left, switch2, False) + f(node.right, switch2, False) + 1\n",
    "                res2 = f(node.left, not switch2, False) + f(node.right, not switch2, False) + 1\n",
    "                res3 = f(node.left, switch2, True) + f(node.right, switch2, True) + 1\n",
    "                res123 = f(node.left, not switch2, True) + f(node.right, not switch2, True) + 3\n",
    "                return min(res1, res2, res3, res123)\n",
    "            else:  # 当前节点为关灯\n",
    "                res0 = f(node.left, switch2, False) + f(node.right, switch2, False)\n",
    "                res12 = f(node.left, not switch2, False) + f(node.right, not switch2, False) + 2\n",
    "                res13 = f(node.left, switch2, True) + f(node.right, switch2, True) + 2\n",
    "                res23 = f(node.left, not switch2, True) + f(node.right, not switch2, True) + 2\n",
    "                return min(res0, res12, res13, res23)\n",
    "        return f(root, False, False)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def closeLampInTree(self, root: TreeNode) -> int:\n",
    "        @cache\n",
    "        def g(r,a,b):\n",
    "          if r is None:\n",
    "              return 0\n",
    "          res=inf\n",
    "          c=1    \n",
    "          if(a==b and r.val==0) or (not(a==b) and r.val==1):\n",
    "              c=0\n",
    "          if not c:\n",
    "                res=min(g(r.left,a,False)+g(r.right,a,False),g(r.left,a,True)+g(r.right,a,True)+2,g(r.left,not a,True)+g(r.right,not a,True)+2,g(r.left,not a,False)+g(r.right,not a,False)+2)\n",
    "                 \n",
    "          else: \n",
    "                res=min(g(r.left,a,False)+g(r.right,a,False)+1,g(r.left,not a,False)+g(r.right,not a,False)+1,g(r.left,not a,True)+g(r.right,not a,True)+3,g(r.left,a,True)+g(r.right,a,True)+1)\n",
    "          return res\n",
    "        return g(root,False,False)          \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closeLampInTree(self, root: TreeNode) -> int:\n",
    "        @cache  # 记忆化搜索\n",
    "        def f(node: TreeNode, switch2: bool, switch3: bool) -> int:\n",
    "            if node is None:\n",
    "                return 0\n",
    "            if (node.val == 1) == (switch2 == switch3):  # 当前节点为开灯\n",
    "                res1 = f(node.left, switch2, False) + f(node.right, switch2, False) + 1\n",
    "                res2 = f(node.left, not switch2, False) + f(node.right, not switch2, False) + 1\n",
    "                res3 = f(node.left, switch2, True) + f(node.right, switch2, True) + 1\n",
    "                res123 = f(node.left, not switch2, True) + f(node.right, not switch2, True) + 3\n",
    "                return min(res1, res2, res3, res123)\n",
    "            else:  # 当前节点为关灯\n",
    "                res0 = f(node.left, switch2, False) + f(node.right, switch2, False)\n",
    "                res12 = f(node.left, not switch2, False) + f(node.right, not switch2, False) + 2\n",
    "                res13 = f(node.left, switch2, True) + f(node.right, switch2, True) + 2\n",
    "                res23 = f(node.left, not switch2, True) + f(node.right, not switch2, True) + 2\n",
    "                return min(res0, res12, res13, res23)\n",
    "        return f(root, False, False)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closeLampInTree(self, root: TreeNode) -> int:\n",
    "        @cache \n",
    "        def fun(node: TreeNode, op1: bool, op2: bool) -> int:\n",
    "            if node is None:\n",
    "                return 0\n",
    "\n",
    "            s = node.val ^ op1 ^ op2\n",
    "            if s:\n",
    "                a = 1 + fun(node.left, False, op2) + fun(node.right, False, op2)\n",
    "                b = 1 + fun(node.left, True, op2) + fun(node.right, True, op2)\n",
    "                c = 1 + fun(node.left, False, op2 ^ 1) + fun(node.right, False, op2 ^ 1)\n",
    "                d = 3 + fun(node.left, True, op2 ^ 1) + fun(node.right, True, op2 ^ 1)\n",
    "                return min(a, b, c)\n",
    "            else:\n",
    "                a = fun(node.left, False, op2) + fun(node.right, False, op2)\n",
    "                b = 2 + fun(node.left, True, op2) + fun(node.right, True, op2)\n",
    "                c = 2 + fun(node.left, False, op2 ^ 1) + fun(node.right, False, op2 ^ 1)\n",
    "                d = 2 + fun(node.left, True, op2 ^ 1) + fun(node.right, True, op2 ^ 1)\n",
    "                return min(a, b, c, d)\n",
    "\n",
    "        return fun(root, False, False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def closeLampInTree(self, root: TreeNode) -> int:\n",
    "        @cache\n",
    "        def f(node: TreeNode, switch2: bool, switch3: bool) -> int:\n",
    "            if node is None:\n",
    "                return 0\n",
    "            if (node.val == 1) == (switch2 == switch3):\n",
    "                res1 = f(node.left, switch2, False) + f(node.right, switch2, False) + 1\n",
    "                res2 = f(node.left, not switch2, False) + f(node.right, not switch2, False) + 1\n",
    "                res3 = f(node.left, switch2, True) + f(node.right, switch2, True) + 1\n",
    "                res123 = f(node.left, not switch2, True) + f(node.right, not switch2, True) + 3\n",
    "                return min(res1, res2, res3, res123)\n",
    "            else:\n",
    "                res0 = f(node.left, switch2, False) + f(node.right, switch2, False)\n",
    "                res12 = f(node.left, not switch2, False) + f(node.right, not switch2, False) + 2\n",
    "                res13 = f(node.left, switch2, True) + f(node.right, switch2, True) + 2\n",
    "                res23 = f(node.left, not switch2, True) + f(node.right, not switch2, True) + 2\n",
    "                return min(res12, res23, res13, res0)\n",
    "        return f(root, False, False)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closeLampInTree(self, root: TreeNode) -> int:\n",
    "        @cache \n",
    "        def fun(node: TreeNode, op1: bool, op2: bool) -> int:\n",
    "            if node is None:\n",
    "                return 0\n",
    "\n",
    "            s = node.val ^ op1 ^ op2\n",
    "            if s:\n",
    "                a = 1 + fun(node.left, False, op2) + fun(node.right, False, op2)\n",
    "                b = 1 + fun(node.left, True, op2) + fun(node.right, True, op2)\n",
    "                c = 1 + fun(node.left, False, op2 ^ 1) + fun(node.right, False, op2 ^ 1)\n",
    "                return min(a, b, c)\n",
    "            else:\n",
    "                a = fun(node.left, False, op2) + fun(node.right, False, op2)\n",
    "                b = 2 + fun(node.left, True, op2) + fun(node.right, True, op2)\n",
    "                c = 2 + fun(node.left, False, op2 ^ 1) + fun(node.right, False, op2 ^ 1)\n",
    "                d = 2 + fun(node.left, True, op2 ^ 1) + fun(node.right, True, op2 ^ 1)\n",
    "                return min(a, b, c, d)\n",
    "\n",
    "        return fun(root, False, False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def closeLampInTree(self, root: TreeNode) -> int:\n",
    "        @cache  # 记忆化搜索\n",
    "        def f(node: TreeNode, switch2: bool, switch3: bool) -> int:\n",
    "            if node is None:\n",
    "                return 0\n",
    "            if (node.val == 1) == (switch2 == switch3):  # 当前节点为开灯\n",
    "                res1 = f(node.left, switch2, False) + f(node.right, switch2, False) + 1\n",
    "                res2 = f(node.left, not switch2, False) + f(node.right, not switch2, False) + 1\n",
    "                res3 = f(node.left, switch2, True) + f(node.right, switch2, True) + 1\n",
    "                res123 = f(node.left, not switch2, True) + f(node.right, not switch2, True) + 3\n",
    "                return min(res1, res2, res3, res123)\n",
    "            else:  # 当前节点为关灯\n",
    "                res0 = f(node.left, switch2, False) + f(node.right, switch2, False)\n",
    "                res12 = f(node.left, not switch2, False) + f(node.right, not switch2, False) + 2\n",
    "                res13 = f(node.left, switch2, True) + f(node.right, switch2, True) + 2\n",
    "                res23 = f(node.left, not switch2, True) + f(node.right, not switch2, True) + 2\n",
    "                return min(res0, res12, res13, res23)\n",
    "        return f(root, False, False)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def closeLampInTree(self, root: TreeNode) -> int:\n",
    "        @cache  # 记忆化搜索\n",
    "        def f(node: TreeNode, switch2: bool, switch3: bool) -> int:\n",
    "            if node is None:\n",
    "                return 0\n",
    "            if (node.val == 1) == (switch2 == switch3):  # 当前节点为开灯\n",
    "                res1 = f(node.left, switch2, False) + f(node.right, switch2, False) + 1\n",
    "                res2 = f(node.left, not switch2, False) + f(node.right, not switch2, False) + 1\n",
    "                res3 = f(node.left, switch2, True) + f(node.right, switch2, True) + 1\n",
    "                res123 = f(node.left, not switch2, True) + f(node.right, not switch2, True) + 3\n",
    "                return min(res1, res2, res3, res123)\n",
    "            else:  # 当前节点为关灯\n",
    "                res0 = f(node.left, switch2, False) + f(node.right, switch2, False)\n",
    "                res12 = f(node.left, not switch2, False) + f(node.right, not switch2, False) + 2\n",
    "                res13 = f(node.left, switch2, True) + f(node.right, switch2, True) + 2\n",
    "                res23 = f(node.left, not switch2, True) + f(node.right, not switch2, True) + 2\n",
    "                return min(res0, res12, res13, res23)\n",
    "        return f(root, False, False)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import cache\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def closeLampInTree(self, root: TreeNode) -> int:\n",
    "        @cache\n",
    "        def f(node, switch2, switch3):\n",
    "            if node is None:\n",
    "                return 0\n",
    "            if (node.val==1) == (switch2==switch3):\n",
    "                res1=f(node.left, switch2, False) + f(node.right, switch2, False) +1\n",
    "                res2=f(node.left, not switch2, False) + f(node.right, not switch2, False) +1\n",
    "                res3=f(node.left, switch2, True) + f(node.right, switch2, True) +1\n",
    "                res123=f(node.left, not switch2, True) + f(node.right, not switch2, True) +3\n",
    "                return min(res1,res2,res3,res123)\n",
    "            else:\n",
    "                res0=f(node.left, switch2, False) + f(node.right, switch2, False)\n",
    "                res12=f(node.left, not switch2, False) + f(node.right, not switch2, False) +2\n",
    "                res23=f(node.left, not switch2, True) + f(node.right, not switch2, True) +2\n",
    "                res13=f(node.left, switch2, True) + f(node.right, switch2, True) +2\n",
    "                return min(res0,res12,res23,res13)\n",
    "        return f(root, False, False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def closeLampInTree(self, root: TreeNode) -> int:\n",
    "\n",
    "        @cache \n",
    "        def f(node: TreeNode, switch2: bool, switch3: bool) -> int:\n",
    "            if node is None:\n",
    "                return 0\n",
    "            if (node.val == 1) == (switch2 == switch3): \n",
    "                res1 = f(node.left, switch2, False) + f(node.right, switch2, False) + 1\n",
    "                res2 = f(node.left, not switch2, False) + f(node.right, not switch2, False) + 1\n",
    "                res3 = f(node.left, switch2, True) + f(node.right, switch2, True) + 1\n",
    "                res123 = f(node.left, not switch2, True) + f(node.right, not switch2, True) + 3\n",
    "                return min(res1, res2, res3, res123)\n",
    "            else: \n",
    "                res0 = f(node.left, switch2, False) + f(node.right, switch2, False)\n",
    "                res12 = f(node.left, not switch2, False) + f(node.right, not switch2, False) + 2\n",
    "                res13 = f(node.left, switch2, True) + f(node.right, switch2, True) + 2\n",
    "                res23 = f(node.left, not switch2, True) + f(node.right, not switch2, True) + 2\n",
    "                return min(res0, res12, res13, res23)\n",
    "        return f(root, False, False)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def closeLampInTree(self, root: TreeNode) -> int:\n",
    "        @cache\n",
    "        def dfs(node: TreeNode, keepSwitch: bool, keepSwitchAll: bool):\n",
    "            # 空节点直接返回\n",
    "            if node is None: return 0\n",
    "\n",
    "            # 四种选择，注意对子树的影响会传递\n",
    "            state = int(node.val == (keepSwitch == keepSwitchAll))\n",
    "            return min(dfs(node.left, True, keepSwitchAll) + dfs(node.right, True, keepSwitchAll) + state,\n",
    "                dfs(node.left, False, keepSwitchAll) + dfs(node.right, False, keepSwitchAll) + 2 - state,\n",
    "                dfs(node.left, True, not keepSwitchAll) + dfs(node.right, True, not keepSwitchAll) + 2 - state,\n",
    "                dfs(node.left, False, not keepSwitchAll) + dfs(node.right, False, not keepSwitchAll) + 2 + state)\n",
    "        \n",
    "        return dfs(root, True, True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closeLampInTree(self, root: TreeNode) -> int:\n",
    "        @cache  # 记忆化搜索\n",
    "        def f(node: TreeNode, switch2: bool, switch3: bool) -> int:\n",
    "            if node is None:\n",
    "                return 0\n",
    "            if (node.val == 1) == (switch2 == switch3):  # 当前节点为开灯\n",
    "                res1 = f(node.left, switch2, False) + f(node.right, switch2, False) + 1\n",
    "                res2 = f(node.left, not switch2, False) + f(node.right, not switch2, False) + 1\n",
    "                res3 = f(node.left, switch2, True) + f(node.right, switch2, True) + 1\n",
    "                res123 = f(node.left, not switch2, True) + f(node.right, not switch2, True) + 3\n",
    "                return min(res1, res2, res3, res123)\n",
    "            else:  # 当前节点为关灯\n",
    "                res0 = f(node.left, switch2, False) + f(node.right, switch2, False)\n",
    "                res12 = f(node.left, not switch2, False) + f(node.right, not switch2, False) + 2\n",
    "                res13 = f(node.left, switch2, True) + f(node.right, switch2, True) + 2\n",
    "                res23 = f(node.left, not switch2, True) + f(node.right, not switch2, True) + 2\n",
    "                return min(res0, res12, res13, res23)\n",
    "        return f(root, False, False)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closeLampInTree(self, root: TreeNode) -> int:\n",
    "        @cache  # 记忆化搜索\n",
    "        def f(node: TreeNode, switch2: bool, switch3: bool) -> int:\n",
    "            if node is None:\n",
    "                return 0\n",
    "            if (node.val == 1) == (switch2 == switch3):  # 当前节点为开灯\n",
    "                res1 = f(node.left, switch2, False) + f(node.right, switch2, False) + 1\n",
    "                res2 = f(node.left, not switch2, False) + f(node.right, not switch2, False) + 1\n",
    "                res3 = f(node.left, switch2, True) + f(node.right, switch2, True) + 1\n",
    "                res123 = f(node.left, not switch2, True) + f(node.right, not switch2, True) + 3\n",
    "                return min(res1, res2, res3, res123)\n",
    "            else:  # 当前节点为关灯\n",
    "                res0 = f(node.left, switch2, False) + f(node.right, switch2, False)\n",
    "                res12 = f(node.left, not switch2, False) + f(node.right, not switch2, False) + 2\n",
    "                res13 = f(node.left, switch2, True) + f(node.right, switch2, True) + 2\n",
    "                res23 = f(node.left, not switch2, True) + f(node.right, not switch2, True) + 2\n",
    "                return min(res0, res12, res13, res23)\n",
    "        return f(root, False, False)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closeLampInTree(self, root: TreeNode) -> int:\n",
    "        @cache  # 记忆化搜索\n",
    "        def f(node: TreeNode, switch2: bool, switch3: bool) -> int:\n",
    "            if node is None:\n",
    "                return 0\n",
    "            if (node.val == 1) == (switch2 == switch3):  # 当前节点为开灯\n",
    "                res1 = f(node.left, switch2, False) + f(node.right, switch2, False) + 1\n",
    "                res2 = f(node.left, not switch2, False) + f(node.right, not switch2, False) + 1\n",
    "                res3 = f(node.left, switch2, True) + f(node.right, switch2, True) + 1\n",
    "                res123 = f(node.left, not switch2, True) + f(node.right, not switch2, True) + 3\n",
    "                return min(res1, res2, res3, res123)\n",
    "            else:  # 当前节点为关灯\n",
    "                res0 = f(node.left, switch2, False) + f(node.right, switch2, False)\n",
    "                res12 = f(node.left, not switch2, False) + f(node.right, not switch2, False) + 2\n",
    "                res13 = f(node.left, switch2, True) + f(node.right, switch2, True) + 2\n",
    "                res23 = f(node.left, not switch2, True) + f(node.right, not switch2, True) + 2\n",
    "                return min(res0, res12, res13, res23)\n",
    "        return f(root, False, False)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def closeLampInTree(self, root: TreeNode) -> int:\n",
    "        @cache\n",
    "        def dfs(node, op2, op3):\n",
    "            if not node: return 0\n",
    "            if (node.val == 1) == (op2 == op3):\n",
    "                res1 = dfs(node.left, op2, False) + dfs(node.right, op2, False) + 1\n",
    "                res2 = dfs(node.left, not op2, False) + dfs(node.right, not op2, False) + 1\n",
    "                res3 = dfs(node.left, op2, True) + dfs(node.right, op2, True) + 1\n",
    "                res123 = dfs(node.left, not op2, True) + dfs(node.right, not op2, True) + 3\n",
    "                return min(res1, res2, res3, res123)\n",
    "            res0 = dfs(node.left, op2, False) + dfs(node.right, op2, False)\n",
    "            res12 = dfs(node.left, not op2, False) + dfs(node.right, not op2, False) + 2\n",
    "            res13 = dfs(node.left, op2, True) + dfs(node.right, op2, True) + 2\n",
    "            res23 = dfs(node.left, not op2, True) + dfs(node.right, not op2, True) + 2\n",
    "            #print(node, res0, res12, res13, res23)\n",
    "            return min(res0, res12, res13, res23)\n",
    "        return dfs(root, False, False)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closeLampInTree(self, root: TreeNode) -> int:\n",
    "        @cache  # 记忆化搜索\n",
    "        def f(node: TreeNode, switch2: bool, switch3: bool) -> int:\n",
    "            if node is None:\n",
    "                return 0\n",
    "            if (node.val == 1) == (switch2 == switch3):  # 当前节点为开灯\n",
    "                res1 = f(node.left, switch2, False) + f(node.right, switch2, False) + 1\n",
    "                res2 = f(node.left, not switch2, False) + f(node.right, not switch2, False) + 1\n",
    "                res3 = f(node.left, switch2, True) + f(node.right, switch2, True) + 1\n",
    "                res123 = f(node.left, not switch2, True) + f(node.right, not switch2, True) + 3\n",
    "                return min(res1, res2, res3, res123)\n",
    "            else:  # 当前节点为关灯\n",
    "                res0 = f(node.left, switch2, False) + f(node.right, switch2, False)\n",
    "                res12 = f(node.left, not switch2, False) + f(node.right, not switch2, False) + 2\n",
    "                res13 = f(node.left, switch2, True) + f(node.right, switch2, True) + 2\n",
    "                res23 = f(node.left, not switch2, True) + f(node.right, not switch2, True) + 2\n",
    "                return min(res0, res12, res13, res23)\n",
    "        return f(root, False, False)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closeLampInTree(self, root: TreeNode) -> int:\n",
    "        @cache  # 记忆化搜索\n",
    "        def f(node: TreeNode, switch2: bool, switch3: bool) -> int:\n",
    "            if node is None:\n",
    "                return 0\n",
    "            if (node.val == 1) == (switch2 == switch3):  # 当前节点为开灯\n",
    "                res1 = f(node.left, switch2, False) + f(node.right, switch2, False) + 1\n",
    "                res2 = f(node.left, not switch2, False) + f(node.right, not switch2, False) + 1\n",
    "                res3 = f(node.left, switch2, True) + f(node.right, switch2, True) + 1\n",
    "                res123 = f(node.left, not switch2, True) + f(node.right, not switch2, True) + 3\n",
    "                return min(res1, res2, res3, res123)\n",
    "            else:  # 当前节点为关灯\n",
    "                res0 = f(node.left, switch2, False) + f(node.right, switch2, False)\n",
    "                res12 = f(node.left, not switch2, False) + f(node.right, not switch2, False) + 2\n",
    "                res13 = f(node.left, switch2, True) + f(node.right, switch2, True) + 2\n",
    "                res23 = f(node.left, not switch2, True) + f(node.right, not switch2, True) + 2\n",
    "                return min(res0, res12, res13, res23)\n",
    "        return f(root, False, False)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def closeLampInTree(self, root: TreeNode) -> int:\n",
    "        @cache  # 记忆化搜索\n",
    "        def f(node: TreeNode, switch2: bool, switch3: bool) -> int:\n",
    "            if node is None:\n",
    "                return 0\n",
    "            if (node.val == 1) == (switch2 == switch3):  # 当前节点为开灯\n",
    "                res1 = f(node.left, switch2, False) + f(node.right, switch2, False) + 1\n",
    "                res2 = f(node.left, not switch2, False) + f(node.right, not switch2, False) + 1\n",
    "                res3 = f(node.left, switch2, True) + f(node.right, switch2, True) + 1\n",
    "                res123 = f(node.left, not switch2, True) + f(node.right, not switch2, True) + 3\n",
    "                return min(res1, res2, res3, res123)\n",
    "            else:  # 当前节点为关灯\n",
    "                res0 = f(node.left, switch2, False) + f(node.right, switch2, False)\n",
    "                res12 = f(node.left, not switch2, False) + f(node.right, not switch2, False) + 2\n",
    "                res13 = f(node.left, switch2, True) + f(node.right, switch2, True) + 2\n",
    "                res23 = f(node.left, not switch2, True) + f(node.right, not switch2, True) + 2\n",
    "                return min(res0, res12, res13, res23)\n",
    "        return f(root, False, False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree root.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def closeLampInTree(self, root: TreeNode) -> int:\n",
    "        @cache\n",
    "        def dfs(root, switch2, swith3):\n",
    "            if root is None:\n",
    "                return 0\n",
    "            if root.val ^ switch2 ^ swith3:\n",
    "                res1 = dfs(root.left, switch2, False) + dfs(root.right, switch2, False) + 1\n",
    "                res2 = dfs(root.left, not switch2, False) + dfs(root.right, not switch2, False) + 1\n",
    "                res3 = dfs(root.left, switch2, True) + dfs(root.right, switch2, True) + 1\n",
    "                res123 = dfs(root.left, not switch2, True) + dfs(root.right, not switch2, True) + 3\n",
    "                return min(res1, res2, res3, res123)\n",
    "            else:\n",
    "                res0 = dfs(root.left, switch2, False) + dfs(root.right, switch2, False)\n",
    "                res12 = dfs(root.left, not switch2, False) + dfs(root.right, not switch2, False) + 2\n",
    "                res13 = dfs(root.left, switch2, True) + dfs(root.right, switch2, True) + 2\n",
    "                res23 = dfs(root.left, not switch2, True) + dfs(root.right, not switch2, True) + 2\n",
    "                return min(res0, res12, res23, res13)\n",
    "        return dfs(root, False, False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def closeLampInTree(self, root: TreeNode) -> int:\n",
    "        @cache  # 记忆化搜索\n",
    "        def f(node: TreeNode, switch2: bool, switch3: bool) -> int:\n",
    "            if node is None:\n",
    "                return 0\n",
    "            if (node.val == 1) == (switch2 == switch3):  # 当前节点为开灯\n",
    "                res1 = f(node.left, switch2, False) + f(node.right, switch2, False) + 1\n",
    "                res2 = f(node.left, not switch2, False) + f(node.right, not switch2, False) + 1\n",
    "                res3 = f(node.left, switch2, True) + f(node.right, switch2, True) + 1\n",
    "                res123 = f(node.left, not switch2, True) + f(node.right, not switch2, True) + 3\n",
    "                return min(res1, res2, res3, res123)\n",
    "            else:  # 当前节点为关灯\n",
    "                res0 = f(node.left, switch2, False) + f(node.right, switch2, False)\n",
    "                res12 = f(node.left, not switch2, False) + f(node.right, not switch2, False) + 2\n",
    "                res13 = f(node.left, switch2, True) + f(node.right, switch2, True) + 2\n",
    "                res23 = f(node.left, not switch2, True) + f(node.right, not switch2, True) + 2\n",
    "                return min(res0, res12, res13, res23)\n",
    "        return f(root, False, False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def closeLampInTree(self, root: TreeNode) -> int:\n",
    "        #copy 0x3\n",
    "        @cache\n",
    "        def f(node,switch2,switch3):\n",
    "            if node is None:\n",
    "                return 0\n",
    "            if (node.val == 1) == (switch2==switch3):\n",
    "                res1 = f(node.left,switch2,False) + f(node.right,switch2,False) + 1\n",
    "                res2 = f(node.left,not switch2,False) + f(node.right,not switch2,False)+1\n",
    "                res3= f(node.left,switch2,True) + f(node.right,switch2,True) + 1\n",
    "                res123 = f(node.left,not switch2,True) + f(node.right,not switch2,True) + 3\n",
    "                return min(res1,res123,res2,res3)\n",
    "            else:\n",
    "                res0 = f(node.left,switch2,False) + f(node.right,switch2,False)\n",
    "                res12 = f(node.left,not switch2,False) + f(node.right,not switch2,False) +2\n",
    "                res13 = f(node.left,switch2,True)+f(node.right,switch2,True) +2\n",
    "                res23 = f(node.left,not switch2,True) + f(node.right,not switch2,True) +2\n",
    "                return min(res0,res12,res13,res23)\n",
    "        return f(root,False,False)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closeLampInTree(self, root: TreeNode) -> int:\n",
    "        @cache  # 记忆化搜索\n",
    "        def f(node: TreeNode, switch2: bool, switch3: bool) -> int:\n",
    "            if node is None:\n",
    "                return 0\n",
    "            \n",
    "            # 当前节点为开灯\n",
    "            if (node.val == 1) == (switch2 == switch3):\n",
    "                res1 = f(node.left, switch2, False) + f(node.right, switch2, False) + 1\n",
    "                res2 = f(node.left, not switch2, False) + f(node.right, not switch2, False) + 1\n",
    "                res3 = f(node.left, switch2, True) + f(node.right, switch2, True) + 1\n",
    "                res123 = f(node.left, not switch2, True) + f(node.right, not switch2, True) + 3\n",
    "                return min(res1, res2, res3, res123)\n",
    "            \n",
    "            # 当前节点为关灯\n",
    "            else:\n",
    "                res0 = f(node.left, switch2, False) + f(node.right, switch2, False)\n",
    "                res12 = f(node.left, not switch2, False) + f(node.right, not switch2, False) + 2\n",
    "                res13 = f(node.left, switch2, True) + f(node.right, switch2, True) + 2\n",
    "                res23 = f(node.left, not switch2, True) + f(node.right, not switch2, True) + 2\n",
    "                return min(res0, res12, res13, res23)\n",
    "        \n",
    "        return f(root, False, False)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def closeLampInTree(self, root: TreeNode) -> int:\n",
    "        #每个节点的开关由3个元素决定 1: 本身的值 2:父节点是否选了开关2 3:祖先节点使用开关3的次数\n",
    "        #注意 条件2， 3 不能由一个变量表示\n",
    "        #我们发现这个次数可以被压缩成一个boolean， 来表示次数的奇偶性\n",
    "        @cache\n",
    "        def dfs(node, switch2, switch3):\n",
    "            if not node:\n",
    "                return 0\n",
    "            #枚举当前开关是开还是关\n",
    "            #为开\n",
    "            if node.val ^ switch2 ^ switch3 == 1:\n",
    "                #要把当前的灯关掉， 可以选用开关1，2，3 和 123一起选用\n",
    "                op1 = dfs(node.left, switch2, False) + dfs(node.right, switch2, False) + 1\n",
    "                op2 = dfs(node.left, not switch2, False) + dfs(node.right, not switch2, False) + 1\n",
    "                op3 = dfs(node.left, switch2, True) + dfs(node.right, switch2, True) + 1\n",
    "                op123 = dfs(node.left, not switch2, True) + dfs(node.right, not switch2, True) + 3\n",
    "                return min(op1, op2, op3, op123)\n",
    "            \n",
    "            #当前为关\n",
    "            else:\n",
    "                #不开或者开选用两个开关\n",
    "                op_none = dfs(node.left, switch2, False) + dfs(node.right, switch2, False)\n",
    "                op12 = dfs(node.left, not switch2, False) + dfs(node.right, not switch2, False) + 2\n",
    "                op23 = dfs(node.left, not switch2, True) + dfs(node.right, not switch2, True) + 2\n",
    "                op13 = dfs(node.left, switch2, True) + dfs(node.right, switch2, True) + 2\n",
    "                return min(op_none, op12, op23, op13)\n",
    "        return dfs(root, False, False)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def closeLampInTree(self, root: TreeNode) -> int:\n",
    "        @cache\n",
    "        def f(node, switch2, switch3):\n",
    "            if node is None:\n",
    "                return 0\n",
    "            if (node.val==1) == (switch2==switch3):\n",
    "                res1 = f(node.left,switch2,False) + f(node.right, switch2, False) + 1\n",
    "                res2 = f(node.left,not switch2,False) + f(node.right,not switch2, False) +1\n",
    "                res3 = f(node.left,switch2,True) + f(node.right, switch2, True) + 1\n",
    "                res123 = f(node.left,not switch2,True) + f(node.right, not switch2, True) +3\n",
    "                return min(res1,res2,res3,res123)\n",
    "            else:\n",
    "                res0 = f(node.left,switch2,False) + f(node.right,switch2, False) \n",
    "                res12 = f(node.left,not switch2,False) + f(node.right,not switch2, False) + 2\n",
    "                res13 = f(node.left,switch2,True) + f(node.right, switch2, True) + 2\n",
    "                res23 = f(node.left,not switch2,True) + f(node.right,not switch2, True) + 2\n",
    "                return min(res0,res12,res13,res23)\n",
    "        return f(root,False,False)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        return f(root,False,False)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
